/**
 * 给定一个数组，最多改变一个位置
 * 问能够得到的最长非递减子数组长度是多少
 * 
 * 首先求出原数组中每段非递减的长度
 * 其次可知必然只改交界处的两端即可
 * 逐个枚举一下即可 
 */
using pii = pair<int, int>;

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int n = nums.size();
        if(1 == n) return 1;

        vector<pii> vec;
        int k = 0;
        while(1){
            int o = 1;
            while(k + o < n and nums[k + o - 1] <= nums[k + o]){
                ++o;
            }
            vec.emplace_back(k, k + o - 1);
            if((k += o) == n) break;
        }
        int ans = 0;
        for(int i=0;i<vec.size();++i){
            auto c = vec[i].second - vec[i].first + 1;
            ans = max(ans, c);
            if(i > 0){
                auto pre = vec[i - 1].second - vec[i - 1].first + 1; 
                ans = max(ans, pre + 1);
                ans = max(ans, c + 1);
                if(c > 1 and nums[vec[i - 1].second] <= nums[vec[i].first + 1]){
                    ans = max(ans, pre + c);
                }
                if(pre > 1 and nums[vec[i - 1].second - 1] <= nums[vec[i].first]){
                    ans = max(ans, pre + c);
                }
            }
        }
        return ans;
    }
};
©leetcode